/**
 * 
 */
package algorithm.passed2;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Set;

/**
 * @author xyyi
 *
 */
public class WordLadder {

	/**
	Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that:

	Only one letter can be changed at a time
	Each intermediate word must exist in the dictionary

	For example,

	Given:
	start = "hit"
	end = "cog"
	dict = ["hot","dot","dog","lot","log"]

	As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
	return its length 5.

	Note:

	Return 0 if there is no such transformation sequence.
	All words have the same length.
	All words contain only lowercase alphabetic characters.
	 */
    public int ladderLength(String beginWord, String endWord, Set<String> wordDict) {
        if (beginWord.equals(endWord))
            return 1;
            
        final Set<String> cache = new HashSet<String>();
        final Queue<String> queue = new LinkedList<String>();
        queue.offer(beginWord);
        cache.add(beginWord);
        int length = 0;
        
        while (!queue.isEmpty()) {
            for (int i = 0, size = queue.size(); i < size; i++) {
                final String word = queue.poll();
                if (endWord.equals(word))
                    return length + 1;
                if (cache.contains(word) || !wordDict.contains(word))
                    continue;
                final List<String> oneCharChangeWords = getOneCharChangeWord(word, wordDict);
                for (final String oneCharChangeWord : oneCharChangeWords) {
                    queue.offer(oneCharChangeWord);
                    cache.add(oneCharChangeWord);
                }
            }
            length++;
        }
        
        return 0;
    }
    
    private List<String> getOneCharChangeWord(final String word, final Set<String> wordDict) {
        final List<String> words = new ArrayList<>();
        final StringBuilder sb = new StringBuilder(word);
        for (int i = 0, size = sb.length(); i < size; i++) {
            final char currChar = sb.charAt(i);
            for (char ch = 'a'; ch <= 'z'; ch++) {
                if (ch != currChar) {
                    sb.setCharAt(i, ch);
                    final String newWord = sb.toString();
                    if (wordDict.contains(newWord))
                        words.add(newWord);
                }   
            }
            sb.setCharAt(i, currChar);
        }
        
        return words;
    }	
	
	
	// BFS
	public int ladderLength2(String start, String end, Set<String> dict) {

		Set<String> visited = new HashSet<String>();
		Queue<String> queue = new LinkedList<String>();
		queue.offer(start);
		visited.add(start);

		int distance = 2;
		while (!queue.isEmpty()) {

			// each time process all words with same distance with start
			int length = queue.size();
			for (int i = 0; i < length; i++) {
				String word = queue.poll();
				StringBuffer sb = new StringBuffer(word);
				for (int j = 0; j < start.length(); j++) {
					char curr = sb.charAt(j);
					for (char ch = 'a'; ch <= 'z'; ch++) {
						if (ch != curr) {
							sb.setCharAt(j, ch);
							String newWord = sb.toString();
							if (!visited.contains(newWord)
							        && dict.contains(newWord)) {
								if (end.equals(newWord)) {
									return distance;
								}
								queue.offer(newWord);
								visited.add(newWord);
							}
						}
					}
					sb.setCharAt(j, curr);
				}
			}
			distance++;
		}

		return 0;
	}

	/*
	int ladderLength(string start, string end, unordered_set<string> &dict) {
	int ret = 0;
	if (start == end)
	    return ret;

	unordered_set<string> added;
	queue<string> que;
	int lev1 = 1;
	int lev2 = 0;
	que.push(start);
	added.insert(start);

	while (!que.empty()) {
	    string s = que.front();
	    que.pop();
	    --lev1;

	    for (int i = 0; i < s.length(); ++i) {
	        for (int j = 0; j < 26; ++j) {
	            string t = s;
	            t[i] = 'a' + j;
	            if (t == end)
	                return ret + 2;
	            if (dict.find(t) != dict.end()
	                && added.find(t) == added.end()) {
	                que.push(t);
	                added.insert(t);
	                ++lev2;
	            }
	        }
	    }

	    if (lev1 == 0) {
	        ++ret;
	        lev1 = lev2;
	        lev2 = 0;
	    }
	}

	return 0;
	}
	 */

	/**
	 * 
	 */
	public WordLadder() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
